Collision detection in three-dimensional (3D) graphics is the process of determining whether two objects, typically rigid bodies comprising linked polygons such as triangles, are in contact with each other. Usually this is done by having a processor implement an algorithm to calculate whether a triangle of one object conflicts spatially with a triangle of another object. Although there are a variety of approaches to this problem all standard solutions use the processor to execute calculations including testing for object-to-object collisions using a spatial data structure such as an octree and then undertaking a series of geometric calculations to assess polygon-to-polygon collisions for those objects whose bounding volumes are shown to be intersection candidates.
When implemented in a processor such as a central processing unit (CPU) these traditional approaches to collision detection can occupy significant computing resources that, particularly in a 3D gaming context, may be better spent in undertaking CPU-specific tasks such as physics calculations or implementing artificial intelligence routines. Moreover, by implementing collision detection in the CPU rather than a dedicated graphics processor such as a graphical processing unit (GPU) the traditional approaches fail to take advantage of the hardware primitives supported by modern graphics texture sampling hardware.